package chapter2;

/**
 * 算法基础-二分查找
 */
public class HalfSearch {

    static boolean flag = false;

    public static void halfSearch(int[] A, int n, int l, int r) {
        if (l >= r) {
            flag = n == A[l];
            return;
        }
        // 找出中位数
        int i = (l + r) / 2;
        int key = A[i];
        if (n < key) {
            halfSearch(A, n, l, i);
        } else if (n > key) {
            halfSearch(A, n, i + 1, r);
        } else if (n == A[i]) {
            flag = true;
        }

    }

    public static boolean halfSearch1(int[] A, int n) {

        int l = 0;
        int r = A.length - 1;
        // 左右区间收紧
        while (l < r) {
            int i = (l + r) / 2;

            if (A[i] == n) {
                return true;
            } else if (n < A[i]) {
                r = i;
            } else if (n > A[i]) {
                l = i + 1;
            }
        }

        return n == A[l];
    }

    public static boolean contains(int[] A, int n) {
        for (int i = 0; i < A.length; i++) {
            int temp = n - A[i];
            if (halfSearch1(A, temp)) {
                return true;
            }
        }
        return false;
    }

}
